package org.niu.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class CombinationSum2 {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        ArrayList<Integer> list = new ArrayList<>();
        boolean[] visited = new boolean[num.length];
        backtracking(num,target,list,visited);
        return ans;
    }
    void backtracking(int[] num,int target,ArrayList<Integer> list,boolean[] visited){
        if(sumList(list)>target){
            return;
        }
        if(sumList(list)==target&&!ans.contains(list)){
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if(!visited[i]){
                visited[i]=true;
                list.add(num[i]);
                backtracking(num,target,list,visited);
                list.remove(list.size()-1);
                visited[i]=false;
            }
        }
    }
    int sumList(ArrayList<Integer> list){
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            sum += list.get(i);
        }
        return sum;
    }
}
